package dynamic;

public class Ex5 {
    static class Solution {
        public String longestPalindrome(String s) {
           int len;
           if (s == null || (len = s.length()) == 0) return "" ;

           int max = 1/* , i = 0 */, start = 0;
           for (int i = 1; i < len; i++) {
                int r1 = check(s, i - 1, i);
                int r2 = check(s, i, i);
                int t = r1 > r2 ? r1 : r2;
                if (t > max) {
                    max = t;
                    start = i - (max) / 2 - 1;
                }
           }
           System.out.println(start + " " + max);
           return s.substring(start, start + max);
        }

        public int check(String s, int lo, int hi) {
            int len = s.length();
            int i = lo, j = hi, start = lo;
            while (lo >= 0 && hi < len) {
                if (s.charAt(lo) == s.charAt(hi)) {
                    lo--;
                    hi++;
                } else {
                    break;
                }
            }
            return (start - lo - 1) * 2 + j - i + 1;
        }
    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        String re = solution.longestPalindrome("abbc");
        System.out.println(re);
    }
}
